﻿using System;
using System.Collections.Generic;
using System.Linq;
using Algoritmia.DataStructures.Queues;
using Algoritmia.DataStructures.Digraphs;
using Algoritmia.Utils;
using Sets=Algoritmia.DataStructures.Sets;

namespace Algoritmia.Problems.Traversals
{
    public class BreadthFirstTraverser<TVertex,TResult> : IGraphBreadthFirstTraverser<TVertex,TResult>
    {
        private readonly Func<IEnumerable<TVertex>,IFifo<TVertex>> _createFifo;
        private readonly Func<IEnumerable<TVertex>, Sets.ISet<TVertex>> _createSet;

        public BreadthFirstTraverser(Func<IEnumerable<TVertex>,IFifo<TVertex>> createFifo = null,
                                     Func<IEnumerable<TVertex>,Sets.ISet<TVertex>> createSet = null)
        {
            _createFifo = createFifo ?? (items => AlgoritmiaFactory.Fifos<TVertex>.Default);
            _createSet = createSet ?? (items => AlgoritmiaFactory.Sets<TVertex>.Default);
        }

        #region Private Methods

        private static IEnumerable<TResult> InternalTraverse(IDigraph<TVertex> graph, TVertex source, Func<TVertex, TVertex, TResult> visitor,
                                                             Sets.ISet<TVertex> visited, IFifo<TVertex> fifo)
        {
            fifo.Push(source);
            visited.Add(source);
            yield return visitor(source, source);
            while (fifo.Count > 0)
            {
                TVertex current = fifo.Pop();
                foreach (var successor in graph.Successors(current))
                {
                    if (!visited.Contains(successor))
                    {
                        fifo.Push(successor);
                        visited.Add(successor);
                        yield return visitor(current, successor);
                    }
                }
            }
        }

        #endregion

        #region IGraphBreadthFirstTraverser<TVertex,TResult> Members
        /// <summary>
        /// Breadth First Traverse Algorithm Implementation, with a source vertex.
        /// </summary>
        /// <param name="graph">The graph where the vertices are stored</param>
        /// <param name="source">The source vertex of the iteration</param>
        /// <param name="preVisitor">A delegate marking a criterium of conversion between a pair of vertices
        /// and a possible result. If is not passed any value at preVisitor neither postVisitor, returns the successor of the pair.
        /// Annotation: The default delegate is inefficient used with value/struct types.
        /// With that types is better call the method specifying the delegate.
        /// </param>
        /// <returns>A sequence of TResult items.</returns>
        public IEnumerable<TResult> Traverse(IDigraph<TVertex> graph, TVertex source, Func<TVertex, TVertex, TResult> preVisitor = null,
            Func<TVertex, TVertex, TResult> postVisitor = null)
        {
            if (preVisitor == null && postVisitor == null)
                preVisitor = GetVisitorFunction(preVisitor);
            var fifo = _createFifo(graph.V);
            var visited = _createSet(graph.V);
            if (preVisitor != null)
            {
                return InternalTraverse(graph, source, preVisitor, visited, fifo);    
            }
            return InternalTraverse(graph, source, postVisitor, visited, fifo).Reverse();
        }

        /// <summary>
        /// Executes a Breadth First Traverse with all the graph vertices as source.
        /// </summary>
        /// <param name="graph">The graph with the data to traverse.</param>
        /// <param name="visitor">A delegate marking a criterium of conversion between a pair of vertices
        /// and a possible result. If is not passed any value, returns the successor of the pair.
        /// Annotation: The default delegate is inefficient used with value/struct types.
        /// With that types is better call the method specifying the delegate.
        /// </param>
        /// <returns>A sequence of TResult items, following the values injected with the visitor parameter.</returns>
        public IEnumerable<TResult> FullTraverse(IDigraph<TVertex> graph, Func<TVertex, TVertex, TResult> preVisitor = null, Func<TVertex, TVertex, TResult> postVisitor = null)
        {
            if (preVisitor == null && postVisitor == null)
                preVisitor = GetVisitorFunction(preVisitor);
            var fifo = _createFifo(graph.V);
            var visited = _createSet(graph.V);
            if (preVisitor != null)
            {
                foreach (var v in graph.V)
                {
                    if (!visited.Contains(v))

                        foreach (var c in InternalTraverse(graph, v, preVisitor, visited, fifo))
                        {
                            yield return c;
                        }
                }
            }
            else // if (postVisitor != null)
            {
                foreach (var v in graph.V)
                {
                    if (!visited.Contains(v))

                        foreach (var c in InternalTraverse(graph, v, postVisitor, visited, fifo).Reverse())
                        {
                            yield return c;
                        }
                }
            }
        }

        private static Func<TVertex, TVertex, TResult> GetVisitorFunction(Func<TVertex, TVertex, TResult> visitor)
        {
            return visitor ?? ((v1, v2) => (TResult)(object)v2);
        }

        public IEnumerable<TResult> TraverseFromSome(IDigraph<TVertex> g, IEnumerable<TVertex> sources, 
                                                     Func<TVertex, TVertex, TResult> visitor = null)
        {
            var fifo = _createFifo(g.V);
            var visited = _createSet(g.V);
            visitor = GetVisitorFunction(visitor);
            foreach (var source in sources)
            {
                fifo.Push(source);
                visited.Add(source);
                yield return visitor(source, source);
            }

            while (fifo.Count > 0)
            {
                TVertex current = fifo.Pop();
                foreach (var successor in g.Successors(current))
                {
                    if (!visited.Contains(successor))
                    {
                        fifo.Push(successor);
                        visited.Add(successor);
                        yield return visitor(current, successor);
                    }
                }
            }
        }

        #endregion

        
    }
}
